#include <iostream>
#include <vector>
using namespace std;

class Banker
{
public:
    Banker(const vector<int> &Resource, const vector<vector<int>> &max_matrix, const vector<vector<int>> &allo_martix)
        : _max_matrix(max_matrix), _allo_martix(allo_martix),_Resource(Resource)
    {
        // 初始化释放数组
        // 初始化需求矩阵
        int row = _max_matrix.size(), col = _max_matrix[0].size();
        _finish.resize(row);
        _need_martix.resize(row, vector<int>(col));
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                _need_martix[i][j] = (_max_matrix[i][j] - _allo_martix[i][j]);
            }
        }
    }
    bool check()
    {
        vector<int> temp_res = _Resource;
        vector<bool> temp_finish = _finish;
        bool is = true; 
        //is用于判断一轮需求矩阵的遍历中是否能找到一个可以释放资源的进程
        //  若可以找到，则is为true，下一次循环也会进入
        //  若找不到，则is为false，下一次循环退出
        while (is)
        {
            is = false;
            for (int i = 0; i < _max_matrix.size(); ++i)
            {
                if (_finish[i] == true)
                    continue;
                int j = 0;
                for (; j < _need_martix[i].size(); ++j)
                {

                    if (_Resource[j] < _need_martix[i][j])
                        break;
                }
                if (j == _max_matrix[i].size())
                {
                    _finish[i] = true;
                    is = true;
                    for (int k = 0; k < _Resource.size(); ++k)
                    {
                        _Resource[k] += _allo_martix[i][k];
                    }
                }
            }
        }
        //走到这里有两种情况：释放完所有进程资源或者资源不够释放剩下的进程
        //  若释放完所有进程资源，则是一个安全序列
        //  若释放不完所有进程资源，则是一个非安全序列
        //  通过已释放数组来判断是哪种情况
        for (int i = 0; i < _finish.size(); ++i)
        {
            if (_finish[i] == false)
            {
                _finish = temp_finish;
                _Resource = temp_res;
                return false;
            }
        }
        // 判断完是否为安全序列后，需要回溯到判断之前的状态
        // 因为该函数只用于判断是否为安全序列，而不参与直接修改原矩阵
        _finish = temp_finish;
        _Resource = temp_res;
        return true;
    }

private:
    vector<vector<int>> _max_matrix;  // 最大需求矩阵
    vector<vector<int>> _allo_martix; // 已分配矩阵
    vector<vector<int>> _need_martix; // 需求矩阵
    vector<bool> _finish;             // 判断是否已释放的数组
    vector<int> _Resource;            // 可用资源
};

int main()
{

    Banker bank({3,3,2},{{6,4,3}, {3,2,4}, {9,0,3}, {2,2,2}, {3,4,3}} ,{ {1,1,0}, {2,0,1}, {4,0,2}, {2,1,1}, {0,1,2} });
    bool ret = bank.check();
    if (ret == true)
    {
        std::cout << "是安全序列" << std::endl;
    }
    else
    {
        std::cout << "是不安全序列" << std::endl;
    }
    return 0;
}